﻿//
// $HeadURL: http://codeka-memcache.googlecode.com/svn/trunk/Codeka.Memcache/ConsistentHasher.cs $
// $Revision: 4 $
// $Author: dean.codeka $     $Date: 2010-02-13 23:21:02 +0000 (Sat, 13 Feb 2010) $
//
// Copyright © 2009-2010 Dean Harding, all rights reserved.
//

using System;
using System.Collections.Generic;
using System.Linq;
using Codeka.Memcache.Config;

namespace Codeka.Memcache
{
    /// <summary>
    /// Hashes keys in such a way that we can return the same <see cref="ServerConfig"/>
    /// each time and ensure that when the server list is reset (via a call to
    /// <b>ResetServers</b>) the keys will <em>mostly</em> continue to map to the same
    /// servers as before.
    /// </summary>
    public class ConsistentHasher
    {
        private SortedList<uint, ServerConfig> servers;
        private uint[] keys;

        /// <summary>
        /// Constructs a new <see cref="ConsistentHasher"/> with the given list of
        /// <see cref="ServerConfig"/>s for the initial population.
        /// </summary>
        /// <param name="servers">The initial collection of <see cref="ServerConfig"/>s
        /// to populate the set with.</param>
        public ConsistentHasher(IEnumerable<ServerConfig> servers)
        {
            Reset(servers);
        }

        /// <summary>
        /// Resets the list of servers in our list to the specified list. We'll do this
        /// in such a way as to invalidate the smallest number of keys possible.
        /// </summary>
        public void Reset(IEnumerable<ServerConfig> newServers)
        {
            servers = new SortedList<uint, ServerConfig>();

            var hasher = new FastHasher();
            foreach (var svr in newServers)
            {
                for (int i = 0; i < svr.Weight; i++)
                {
                    string key = string.Format("{0}-{1}", svr, i);
                    uint hash = hasher.Hash(key);

                    servers[hash] = svr;
                }
            }

            // we'll convert the keys to an array for easy access later
            keys = new List<uint>(servers.Keys).ToArray();
        }

        /// <summary>
        /// Finds the <see cref="ServerConfig"/> that corresponds to the given string key.
        /// The algorithm is such that it'll always return the same server for the same key,
        /// even if the list of servers change.
        /// </summary>
        public ServerConfig GetServer(string key)
        {
            if (string.IsNullOrEmpty(key))
                return null;

            uint hash = new FastHasher().Hash(key);

            int index = Array.BinarySearch(keys, hash);
            if (index < 0)
            {
                // no exact match, find the "nearest" match instead
                index = ~index;
                if (index == 0)
                {
                    // if it's smaller than anything else, use the last server
                    index = keys.Length - 1;
                }
                else if (index >= keys.Length)
                {
                    // if it's bigger than anything else, use the first server
                    index = 0;
                }
            }

            return servers[keys[index]];
        }
    }
}
